#pragma once
#include <utility>
#include <vector>
#include <string>
using namespace std;

template <class T>
struct HashNode{
  typedef HashNode<T> Node;
  T _data;
  Node *_next;

  HashNode(const T& data = T(), Node *next = nullptr)
    :_data(data),
    _next(next)
  {}
};

template <class K>
struct Hashkey{
  size_t operator()(const K& key){
    return (size_t)key;
  }
};

template <>
struct Hashkey<string>{
  size_t operator()(const string& str){
    size_t ret = 0;
    for(char e : str)
    {
      ret += e;
      ret *= 131;
    }
    return ret;
  }
};

template <class K, class T, class Hash, class KofT>
class HashTable;

template <class K, class T, class Hash, class KofT>
class __Hashiterator{
  typedef HashNode<T> Node;
  typedef HashTable<K,T,Hash,KofT> HT;
  typedef __Hashiterator<K,T, Hash, KofT> iterator;
  Node *_pnode;
  HT *_pht;

public:
  __Hashiterator(Node *pnode, HT *pht)
    :_pnode(pnode),
    _pht(pht)
  {}

public:
  T& operator*() const{
    return _pnode->_data;
  }

  T* operator->() const{
    return &_pnode->_data;
  }

  bool operator==(const iterator& it) const{
    return it._pnode == _pnode;
  }

  bool operator!=(const iterator& it) const{
    return it._pnode != _pnode;
  }

  iterator& operator++(){
    if(_pnode->_next != nullptr)
    {
      _pnode = _pnode->_next;
    }
    else
    {
      KofT kot;
      Hash hash;
      size_t hashi = hash(kot(_pnode->_data)) % _pht->_table.size();
      int i = hashi + 1;
      for(; i<_pht->_table.size(); ++i)
      {
        if(_pht->_table[i] != nullptr)
        {
          _pnode = _pht->_table[i];
          break;
        }
      }
      if(i == _pht->_table.size())
        _pnode = nullptr;
    }
    return *this;
  }

  iterator& operator--(){
    if(_pnode == nullptr)
    {
      size_t i = _pht->_table.size()-1;
      for(; i>=0; --i)
      {
        if(_pht->_table[i] != nullptr)
        {
          Node *cur = _pht->_table[i];
          while(cur->_next != nullptr)
          {
            cur = cur->_next;
          }
          _pnode = cur;
          return *this;
        }
      }
    }

    KofT kot;
    Hash hash;
    size_t hashi = hash(kot(_pnode->_data)) % _pht->_table.size();
    if(_pht->_table[hashi] != _pnode)
    {
      Node *cur = _pht->_table[hashi];
      while(cur->_next != _pnode)
      {
        cur = cur->_next;
      }
      _pnode = cur;
    }
    else
    {
      size_t i = hashi - 1;
      for(; i>=0; --i)
      {
        if(_pht->_table[i] != nullptr)
        {
          Node* cur = _pht->_table[i];
          while(cur->_next != nullptr)
          {
            cur = cur->_next;
          }
          _pnode = cur;
          break;
        }
      }
    }
    return *this;
  }

  iterator operator++(int){
    iterator it(*this);
    ++*this;
    return it;
  }
  
  iterator operator--(int){
    iterator it(*this);
    --*this;
    return it;
  }
};

template <class K, class T, class Hash, class KofT>
class HashTable{
  typedef HashNode<T> Node;
  vector<Node*> _table;
  size_t _size = 0;

  template <class k, class t, class hash, class kofT>
  friend class __Hashiterator;

public:
  typedef __Hashiterator<K, T,Hash,KofT> iterator;
  iterator begin(){
    for(int i=0; i<_table.size(); ++i)
    {
      if(_table[i] != nullptr)
        return iterator(_table[i], this);
    }
    return iterator(nullptr, this);
  }

  iterator end(){
    return iterator(nullptr, this);
  }
  pair<iterator, bool> insert(const T& data){
    KofT kot;
    Hash hash;
    //去重
    iterator ret = find(kot(data));
    if(ret != end())
        return make_pair(ret, false);
    //扩容
    if(_size == _table.size())
    {
      size_t newsize = __stl_next_prime(_table.size()); 
      vector<Node*> newtable;
      newtable.resize(newsize);
      for(size_t i=0; i<_table.size(); ++i)
      {
        Node *cur = _table[i];
        Node *next = nullptr;
        while(cur != nullptr)
        {
          size_t hashi = hash(kot(cur->_data)) % newsize;
          next = cur->_next;
          cur->_next = newtable[hashi]; 
          newtable[hashi] = cur;
          cur = next;
        }
        _table[i] = nullptr;
      }
      swap(_table, newtable);
    }
    //插入
    size_t hashi = hash(kot(data)) % _table.size();
    Node *newnode = new Node(data);
    newnode->_next = _table[hashi];
    _table[hashi] = newnode;
    ++_size;
    return make_pair(iterator(newnode, this), true);
  }

  iterator find(const K& key){
    if(_table.size() == 0)
      return end();
    
    Hash hash;
    KofT kot;
    size_t hashi = hash(key) % _table.size();
    Node *cur = _table[hashi];
    while(cur != nullptr)
    {
      if(kot(cur->_data) == key)
      {
        return iterator(cur, this);
      }
      cur = cur->_next;
    }
    return end();
  }

  bool erase(const K& key){
    if(_table.size() == 0)
      return false;

    Hash hash;
    KofT kot;
    size_t hashi = hash(key) % _table.size();
    Node *cur = _table[hashi];
    Node *prev = nullptr;
    while(cur != nullptr)
    {
      if(key == kot(cur->_data))
      {
        if(cur == _table[hashi])
          _table[hashi] = cur->_next;
        else
          prev->_next = cur->_next;
        delete cur; 
        --_size;
        return true;
      }
      prev = cur;
      cur = cur->_next;
    }
    return false;
  }

  size_t size(){
    return _size;
  }

private:
  inline size_t __stl_next_prime(size_t n)
  {
    static const int __stl_num_primes = 28;
    static const size_t __stl_prime_list[__stl_num_primes] =
    {
      53,         97,         193,       389,       769,
      1543,       3079,       6151,      12289,     24593,
      49157,      98317,      196613,    393241,    786433,
      1572869,    3145739,    6291469,   12582917,  25165843,
      50331653,   100663319,  201326611, 402653189, 805306457, 
      1610612741, 3221225473, 4294967291
    };
    for(int i=0; i<__stl_num_primes; ++i)
    {
      if(__stl_prime_list[i] > n)
      {
        return __stl_prime_list[i];
      }
    }
    return -1;
  }
};
